平均
题目 平均
思路分析
若n=10 就要让0-9全都出现一次 若n为20 就1-9全出现两次
贪心策略1：
由n/10可以确定出各个数应该出现的次数 令其为mid 只存在大于mid的补给小于mid的 不存在大于mid补给大于mid 小于mid补给小于mid 小于mid补给大于mid的情况 所以只需要考虑所有大于mid的数 它们的花费代价
贪心策略2：
更改不同的数 花费的代价不同 优先更改花费小的数
问题解决
代码实现
一开始不确定map能否嵌套优先队列 这代码给我写笑了
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> zero;
priority_queue<int,vector<int>,greater<int>> one;
priority_queue<int,vector<int>,greater<int>> two;
priority_queue<int,vector<int>,greater<int>> three;
priority_queue<int,vector<int>,greater<int>> four;
priority_queue<int,vector<int>,greater<int>> five;
priority_queue<int,vector<int>,greater<int>> six;
priority_queue<int,vector<int>,greater<int>> seven;
priority_queue<int,vector<int>,greater<int>> eight;
priority_queue<int,vector<int>,greater<int>> nine;
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++){
int a,b;cin>>a>>b;
switch(a)
{
case 0:{
zero.push(b);
break;
}
case 1:{
one.push(b);
break;
}
case 2:{
two.push(b);
break;
}
case 3:{
three.push(b);
break;
}
case 4:{
four.push(b);
break;
}
case 5:{
five.push(b);
break;
}
case 6:{
six.push(b);
break;
}
case 7:{
seven.push(b);
break;
}
case 8:{
eight.push(b);
break;
}
case 9:{
nine.push(b);
break;
}
}
}
int mid=n/10;
long long res=0;
while(zero.size()>mid){
res+=zero.top();
zero.pop();
}
while(one.size()>mid){
res+=one.top();
one.pop();
}
while(two.size()>mid){
res+=two.top();
two.pop();
}
while(three.size()>mid){
res+=three.top();
three.pop();
}
while(four.size()>mid){
res+=four.top();
four.pop();
}
while(five.size()>mid){
res+=five.top();
five.pop();
}
while(six.size()>mid){
res+=six.top();
six.pop();
}
while(seven.size()>mid){
res+=seven.top();
seven.pop();
}
while(eight.size()>mid){
res+=eight.top();
eight.pop();
}
while(nine.size()>mid){
res+=nine.top();
nine.pop();
}
cout<<res;
return 0;
}
map嵌套priority_queue
#include<bits/stdc++.h>
using namespace std;
map<int,priority_queue<int,vector<int>,greater<int>>> pqmap;
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++){
int a,b;cin>>a>>b;
pqmap[a].push(b);
}
int mid=n/10;
long long res=0;
for(auto &entry:pqmap){
auto &pq=entry.second;
while(pq.size()>mid){
res+=pq.top();
pq.pop();
}
}
cout<<res;
return 0;
}
虽然但是 上面代码766ms 下面889ms （bushi）
💬 评论